package cn.ducis.macaw.core.staticflies.file;

import java.util.*;

import cn.ducis.macaw.util.basic.Assert;

@Deprecated
public class BPlusTreeOld {
	/**
	 * B+树节点
	 * 
	 * @version 1.0
	 */
	public class Node {
		private boolean isLeaf;
		// 节点的子节点列表（非叶子节点肯定有子节点）
		private List<Node> children;
		// 非叶子节点键表
		private List<Integer> keyList;
		// 节点键值对
		private List<KeyAndValue> keyAndValues;
		// 叶子节点的后节点
		private Node nextNode = null;
		// 叶子节点的前节点
		private Node preNode = null;
		// 节点的父节点
		private Node fatherNode = null;

		// 创建新节点
		public Node(boolean isLeaf) {
			if (isLeaf) {
				this.keyAndValues = new LinkedList<>();
				this.isLeaf = true;
			} else {
				this.children = new LinkedList<>();
				this.keyList = new LinkedList<>();
				this.isLeaf = false;
			}
		}

		// 非叶子节点肯定有子节点
		public boolean isLeaf() {
			return children == null;
		}
	}

	/**
	 * B+树键值
	 * 
	 * @version 1.0
	 */
	public static class KeyAndValue {
		private int key;
		private Object value;

		private void setValue(Object value) {
			this.value = value;
		}

		private KeyAndValue(int key, Object value) {
			this.key = key;
			this.value = value;
		}
	}

	/**
	 * B+树节点排序比较器
	 * 
	 * @version 1.0
	 */
	public class TreeNodeComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			return o1 - o2;
		}
	}

	private int order;
	private Node root = null;
	private Node head = null;

	/**
	 * B+树有参构造函数
	 * 
	 * @param order
	 *            B+树的阶数
	 */
	public BPlusTreeOld(int order) {
		if (order < 3) {
			System.out.println("order must >2");
			System.exit(0);
		}
		this.order = order;
	}

	/**
	 * 查找<br>
	 * 从指定根节点开始查找键为传参对象的值
	 * 
	 * @param key
	 * @param root
	 * @return 指定键在树中对应的值
	 */
	private Object search(int key, Node root) {
		// 指定根节点为空时默认从整棵树的根节点开始查找
		if (root == null) {
			Assert.notNull(this.root, "搜索的树不能为空");
			root = this.root;
		}

		// 如果根节点是叶子节点
		if (root.isLeaf()) {
			// 二分查找
			int index = binarySearch(root, key, root.isLeaf);
			// 查找到了在叶子结点中取出对应的值，未找到则返回null
			return (index >= 0) ? root.keyAndValues.get(index - 1).value : null;
		}

		// 非叶子节点
		// 如果key小于最左边的key,沿着第一个子节点继续搜索
		if (key - root.keyList.get(0) < 0)
			return search(key, root.children.get(0));
		// 如果key大于等于最右边key，沿着最后一个子节点继续搜索
		else if (key - root.keyList.get(root.keyList.size() - 1) >= 0) {
			return search(key, root.children.get(root.children.size() - 1));
		}
		// 否则沿比key大的前一个子节点继续搜索
		else {
			// 二分查找
			int index = binarySearch(root, key, root.isLeaf);
			// 递归查找到叶子结点
			return search(key, root.children.get(index));
		}
	}

	/**
	 * 二分查找
	 * 
	 * @param root
	 *            查找的节点
	 * @param key
	 *            要查找的键
	 * @param isLeaf
	 *            查找节点是否是叶子节点
	 * @return 查找结果
	 */
	private int binarySearch(Node root, int key, boolean isLeaf) {
		int compare, low = 0, mid = 0, high;
		// 叶子结点和非叶子节点有所区别（叶子结点即存了键也存了值）
		if (isLeaf)
			high = root.keyAndValues.size() - 1;
		else
			high = root.keyList.size() - 1;

		while (low <= high) {
			mid = (low + high) / 2;
			if (isLeaf) {
				compare = root.keyAndValues.get(mid).key - key;
			} else {
				compare = root.keyList.get(mid) - key;
			}
			if (compare == 0)
				// 非叶子节点查找到了要从第mid+1个孩子结点继续往下查找直到叶子结点（叶子结点记得-1）
				return mid + 1;
			else if (compare < 0)
				low = mid + 1;
			else
				high = mid - 1;
		}
		if (isLeaf)
			// 是叶子结点未找到返回-1用于判断
			return -1;
		else
			// 非叶子节点返回low往对应下层孩子结点继续查找
			return low;
	}

	/**
	 * 插入<br>
	 * 键在树中-更新value<br>
	 * 不在-插入 非叶子节点子节点列表长度>order,需要分裂成两个节点（父节点增加索引）--回溯平衡
	 */

	/**
	 * 判断节点中是否存在key键
	 * 
	 * @param root
	 * @param key
	 * @return 存在返回下标，不存在返回-1
	 */
	private Integer isExist(Node root, int key) {
		Assert.notNull(root, "待判断结点不能为空");
		// 二分法
		int locate = binarySearch(root, key, root.isLeaf);
		if (locate >= 0)
			return locate - 1;
		return locate;
	}

	/**
	 * 在不满的叶子节点插入键值（不存在相等key情况）
	 * 
	 * @param root
	 * @param kv
	 */
	private void insertInLeaf(Node root, KeyAndValue kv) {
		// 二分查找，插入
		int low = 0, high = root.keyAndValues.size() - 1, mid;
		int comp;
		while (low <= high) {
			mid = (low + high) / 2;
			comp = root.keyAndValues.get(mid).key - kv.key;
			if (comp > 0)
				high = mid - 1;
			else
				low = mid + 1;
		}
		root.keyAndValues.add(low, kv);
	}

	/**
	 * 插入操作（key不重复，key重复则更新value）
	 * 
	 * @param root
	 * @param kv
	 */
	private void insert(Node root, KeyAndValue kv) {
		// 树空，直接插入根节点
		if (root == null) {
			Node newNode = new Node(true);
			this.root = newNode;
			this.head = newNode;
			this.root.keyAndValues.add(kv);
			return;
		}
		// 如果插入的是叶子节点
		if (root.isLeaf()) {
			// 判断键是否在结点中
			int index = isExist(root, kv.key);
			// 键已在结点中，更新值
			if (index != -1) {
				root.keyAndValues.get(index).setValue(kv.value);
				return;
			}
			// 不在结点中，且结点有位置，插入
			if (root.keyAndValues.size() < order) {
				insertInLeaf(root, kv);
				return;
			}
			// 不在节点中且结点已满，先插入进去，再分裂为两个结点
			// 左边的继承整除2的一半（比如3个继承（3+1）/2=2个，4个继承（4+1）/2=2个）
			insertInLeaf(root, kv);
			int leftsize = root.keyAndValues.size() / 2;
			Node left = new Node(true);
			Node right = new Node(true);
			for (int i = 0; i < leftsize; i++) {
				left.keyAndValues.add(root.keyAndValues.get(i));
			}
			for (int i = 0; i < leftsize; i++) {
				right.keyAndValues.add(root.keyAndValues.get(leftsize + i));
			}
			// 调整指针（连接）
			if (root.preNode == null) {
				this.head = left;
			} else {
				left.preNode = root.preNode;
				root.preNode.nextNode = left;
			}
			if (root.nextNode != null) {
				root.nextNode.preNode = right;
				right.nextNode = root.nextNode;
			}
			left.nextNode = right;
			right.preNode = left;
			root.preNode = null;
			root.nextNode = null;
			// 调整父节点
			// 如果不是根节点，找到父节点中root的位置x,删除，分别在x上插入，right,left
			if (root.fatherNode != null) {
				// 调整子节点列表
				int index2 = root.fatherNode.children.indexOf(root);
				left.fatherNode = root.fatherNode;
				right.fatherNode = root.fatherNode;
				root.fatherNode.children.remove(index2);
				root.fatherNode.children.add(index2, right);
				root.fatherNode.children.add(index2, left);
				// 调整键表
				int index3 = 0;
				if (root.isLeaf()) {
					root.fatherNode.keyList.add(right.keyAndValues.get(0).key);
					Collections.sort(root.fatherNode.keyList, new TreeNodeComparator());
				} else {
					index3 = root.fatherNode.keyList.indexOf(root.keyList.get(0));
					if (index3 >= 0) {
						root.fatherNode.keyList.remove(index3);
						root.fatherNode.keyList.add(index3, right.keyList.get(0));
						root.fatherNode.keyList.add(index3, left.keyList.get(0));
						Collections.sort(root.fatherNode.keyList, new TreeNodeComparator());
					} else {
						root.fatherNode.keyList.add(right.keyList.get(0));
						Collections.sort(root.fatherNode.keyList, new TreeNodeComparator());
					}
				}
				// 向上回溯，调整父节点
				updateInsert(root.fatherNode);
				root.fatherNode = null;
			} else {
				Node newNode = new Node(false);
				this.root = newNode;
				left.fatherNode = newNode;
				right.fatherNode = newNode;
				newNode.children.add(left);
				newNode.children.add(right);
				if (right.isLeaf()) {
					newNode.keyList.add(right.keyAndValues.get(0).key);
					Collections.sort(newNode.keyList, new TreeNodeComparator());
				} else {
					newNode.keyList.add(right.keyList.get(0));
					Collections.sort(newNode.keyList, new TreeNodeComparator());
				}
				if (root.isLeaf())
					root.keyAndValues = null;
			}
			return;
		}
		// 不是叶子节点，遍历找到叶子节点
		// 非叶子节点
		// 如果key小于最左边的key,沿着第一个子节点继续搜索
		if (kv.key - root.keyList.get(0) < 0)
			insert(root.children.get(0), kv);
		// 如果key大于等于最右边key，沿着最后一个子节点继续搜索
		else if (kv.key - root.keyList.get(root.keyList.size() - 1) >= 0) {
			insert(root.children.get(root.children.size() - 1), kv);

		}
		// 否则沿比key大的前一个子节点继续搜索
		else {
			// 二分查找
			int index = binarySearch(root, kv.key, root.isLeaf);
			insert(root.children.get(index), kv);
			// int low = 0, high = root.keyList.size() - 1, mid = 0;
			// int comp;
			// while (low <= high) {
			// mid = (low + high) / 2;
			// comp = root.keyList.get(mid) - kv.key;
			// if (comp == 0)
			// insert(root.children.get(mid + 1), kv);
			// else if (comp < 0)
			// low = mid + 1;
			// else
			// high = mid - 1;
			// }
			// insert(root.children.get(low), kv);
		}
	}

	// 插入节点后回溯更新父节点
	private void updateInsert(Node root) {
		if (root.children.size() > order) {
			int rightsize = root.children.size() / 2 + root.children.size() % 2;
			int leftsize = root.children.size() / 2;
			Node left = new Node(false);
			Node right = new Node(false);
			for (int i = 0; i < leftsize; i++) {
				left.children.add(root.children.get(i));
				root.children.get(i).fatherNode = left;
			}
			for (int i = 0; i < rightsize; i++) {
				right.children.add(root.children.get(leftsize + i));
				root.children.get(leftsize + i).fatherNode = right;
			}
			for (int i = 0; i < leftsize - 1; i++) {
				left.keyList.add(root.keyList.get(i));
			}
			for (int i = 0; i < rightsize - 1; i++) {
				right.keyList.add(root.keyList.get(leftsize + i));
			}
			// 如果不是根节点
			if (root.fatherNode != null) {
				// 调整子节点列表
				int index2 = root.fatherNode.children.indexOf(root);
				left.fatherNode = root.fatherNode;
				right.fatherNode = root.fatherNode;
				root.fatherNode.children.remove(index2);
				root.fatherNode.children.add(index2, right);
				root.fatherNode.children.add(index2, left);
				// 调整键表
				int index3 = 0;
				if (root.isLeaf()) {
					root.fatherNode.keyList.add(right.keyAndValues.get(0).key);
					Collections.sort(root.fatherNode.keyList, new TreeNodeComparator());
				} else {
					index3 = root.fatherNode.keyList.indexOf(root.keyList.get(0));
					if (index3 >= 0) {
						root.fatherNode.keyList.remove(index3);
						root.fatherNode.keyList.add(index3, right.keyList.get(0));
						root.fatherNode.keyList.add(index3, left.keyList.get(0));
						Collections.sort(root.fatherNode.keyList, new TreeNodeComparator());
					} else {
						root.fatherNode.keyList.add(right.keyList.get(0));
						Collections.sort(root.fatherNode.keyList, new TreeNodeComparator());
					}

				}
				// 向上回溯，调整父节点
				updateInsert(root.fatherNode);
				root.fatherNode = null;
			} else {
				Node newNode = new Node(false);
				this.root = newNode;
				left.fatherNode = newNode;
				right.fatherNode = newNode;
				newNode.children.add(left);
				newNode.children.add(right);
				newNode.keyList.add(root.keyList.get(leftsize - 1));
				Collections.sort(newNode.keyList, new TreeNodeComparator());
				root.keyAndValues = null;
			}
		}
	}

	/**
	 * 删除<br>
	 * 当非叶子节点子节点列表小于order/2或者小于2,需要合并节点
	 * 
	 * @param root
	 * @param key
	 */
	public void delete(Node root, int key) {
		// 键不在树中
		Object result = this.search(key, this.root);
		Assert.notNull(result, "索引树中不存在要删除的键值对");
		// 键在树中
		// 如果是叶子节点
		if (root.isLeaf()) {
			int index = isExist(root, key);
			// ①如果是叶子节点,且是根节点则直接删
			if (root.fatherNode == null) {
				root.keyAndValues.remove(index);
				return;
			}
			// ②如果删后不需要合并节点，直接删
			if (root.keyAndValues.size() > order / 2 && root.keyAndValues.size() > 2) {
				root.keyAndValues.remove(index);
				return;
			}
			// ③如果自身关键字数数=order/2(小于order/2的情况应该不存在，删除后就不平衡了)且，
			// 前一个节点关键字数>2，则从前面借一个在删
			if (root.preNode != null && root.preNode.fatherNode == root.fatherNode
					&& root.preNode.keyAndValues.size() > order / 2 && root.preNode.keyAndValues.size() > 2) {
				int index1 = root.preNode.keyAndValues.size();
				root.keyAndValues.add(0, root.preNode.keyAndValues.remove(index1 - 1));
				int index2 = root.fatherNode.children.indexOf(root.preNode);
				root.fatherNode.keyList.set(index2, root.keyAndValues.get(0).key);
				// 新增了一个节点index+1
				root.keyAndValues.remove(index + 1);
				return;
			}
			// ④如果自身关键字数数=order/2(小于order/2的情况应该不存在，删除后就不平衡了)且，
			// 后一个节点关键字数>2，则从后面借一个在删
			if (root.nextNode != null && root.nextNode.fatherNode == root.fatherNode
					&& root.nextNode.keyAndValues.size() > order / 2 && root.nextNode.keyAndValues.size() > 2) {
				root.keyAndValues.add(root.nextNode.keyAndValues.remove(0));
				int index3 = root.fatherNode.children.indexOf(root);
				root.fatherNode.keyList.set(index3, root.nextNode.keyAndValues.get(0).key);
				// 尾部添加，index不变
				root.keyAndValues.remove(index);
				return;
			}

			// ⑤上述不成立即借不到节点，只能自己合并给别人了
			// 前节点非空，与前节点合并
			if (root.preNode != null && root.preNode.fatherNode == root.fatherNode
					&& (root.preNode.keyAndValues.size() <= order / 2 || root.preNode.keyAndValues.size() <= 2)) {
				root.keyAndValues.remove(index);
				for (int i = 0; i < root.keyAndValues.size(); i++) {
					root.preNode.keyAndValues.add(root.keyAndValues.get(i));
				}
				root.keyAndValues = root.preNode.keyAndValues;
				root.fatherNode.children.remove(root.preNode);
				root.preNode.fatherNode = null;
				root.preNode.keyAndValues = null;
				// 更新链表
				if (root.preNode.preNode != null) {
					Node p = root.preNode;
					p.preNode.nextNode = root;
					root.preNode = p.preNode;
					p.preNode = null;
					p.nextNode = null;
				} else {
					this.head = root;
					root.preNode.nextNode = null;
					root.preNode = null;
				}
				// 如果父节点符合平衡，退出
				root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
				if ((root.fatherNode.fatherNode != null
						&& (root.fatherNode.children.size() >= order / 2 && root.fatherNode.children.size() >= 2))
						|| root.fatherNode.fatherNode == null && root.fatherNode.children.size() >= 2) {
					return;
				}
				// 回溯更新父节点
				updateDelete(root.fatherNode);
				return;
			}

			// ⑥到这一步说明前阶段空了
			// 同后节点合并。
			if (root.nextNode != null && root.nextNode.fatherNode == root.fatherNode
					&& (root.nextNode.keyAndValues.size() <= order / 2 || root.nextNode.keyAndValues.size() <= 2)) {
				root.keyAndValues.remove(index);
				for (int i = 0; i < root.nextNode.keyAndValues.size(); i++) {
					root.keyAndValues.add(root.keyAndValues.get(i));
				}
				root.nextNode.fatherNode = null;
				root.nextNode.keyAndValues = null;
				root.fatherNode.children.remove(root.nextNode);
				// 更新链表
				if (root.nextNode.nextNode != null) {
					Node p = root.nextNode;
					p.nextNode.preNode = root;
					root.nextNode = p.nextNode;
					p.preNode = null;
					p.nextNode = null;
				} else {
					root.preNode = null;
					root.nextNode = null;
				}
				// 更新父节点链表
				root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
				if ((root.fatherNode.fatherNode != null
						&& (root.fatherNode.children.size() >= order / 2 && root.fatherNode.children.size() >= 2))
						|| root.fatherNode.fatherNode == null && root.fatherNode.children.size() >= 2) {
					return;
				}
				updateDelete(root.fatherNode);
				return;
			}

		}
		// 如果不是叶子节点，就遍历到叶子节点
		// 非叶子节点
		// 如果key小于最左边的key,沿着第一个子节点继续搜索
		if (key - root.keyList.get(0) < 0)
			delete(root.children.get(0), key);
		// 如果key大于等于最右边ke'y，沿着最后一个子节点继续搜索
		else if (key - root.keyList.get(root.keyList.size() - 1) >= 0) {
			delete(root.children.get(root.children.size() - 1), key);
		}
		// 否则沿比key大的前一个子节点继续搜索
		else {
			// 二分查找
			int index = binarySearch(root, key, root.isLeaf);
			delete(root.children.get(index), key);
			// int low = 0, high = root.keyList.size() - 1, mid = 0;
			// int comp;
			// while (low <= high) {
			// mid = (low + high) / 2;
			// comp = root.keyList.get(mid) - key;
			// if (comp == 0)
			// delete(root.children.get(mid + 1), key);
			// else if (comp < 0)
			// low = mid + 1;
			// else
			// high = mid - 1;
			// }
			// delete(root.children.get(low), key);
		}

	}

	/**
	 * 删除后回溯更新-平衡
	 * @param root
	 */
	private void updateDelete(Node root) {
		// 如果节点<order/2或者<小于2，
		if (root.children.size() < order / 2 || root.children.size() < 2) {
			if (root.fatherNode == null) {
				if (root.children.size() > 2)
					return;
				Node p = root.children.get(0);
				this.root = p;
				p.fatherNode = null;
				root.keyList = null;
				root.keyList = null;
				return;
			}
			// 计算前后节点
			int currIdx = root.fatherNode.children.indexOf(root);
			int preIdx = currIdx - 1;
			int nextIdx = currIdx + 1;
			Node preNode = null, nextNode = null;
			if (preIdx >= 0)
				preNode = root.fatherNode.children.get(preIdx);
			if (nextIdx < root.fatherNode.children.size())
				nextNode = root.fatherNode.children.get(nextIdx);

			// 前一个节点关键字数>2，则从前面借一个在删
			if (preNode != null && preNode.children.size() > order / 2 && preNode.children.size() > 2) {
				int index1 = preNode.children.size() - 1;
				Node borrow = preNode.children.get(index1);
				preNode.children.remove(index1);
				borrow.fatherNode = root;
				root.children.add(0, borrow);

				int index2 = root.fatherNode.children.indexOf(preNode);
				root.keyList.add(0, root.fatherNode.keyList.get(index2));
				root.fatherNode.keyList.set(index2, preNode.keyList.remove(index1 - 1));
				return;
			}
			// ④如果自身关键字数数=order/2(小于order/2的情况应该不存在，删除后就不平衡了)且，
			// 后一个节点关键字数>2，则从后面借一个在删
			if (nextNode != null && nextNode.children.size() > order / 2 && nextNode.children.size() > 2) {
				Node borrow = nextNode.children.get(0);
				nextNode.children.remove(0);
				borrow.fatherNode = root;
				root.children.add(borrow);
				int index3 = root.fatherNode.children.indexOf(root);
				root.keyList.add(root.fatherNode.keyList.get(index3));
				root.fatherNode.keyList.set(index3, nextNode.keyList.remove(0));
				return;
			}

			// ⑤上述不成立即借不到节点，只能自己合并给别人了
			// 前节点非空，与前节点合并
			if (preNode != null && (preNode.children.size() <= order / 2 || preNode.children.size() <= 2)) {
				for (int i = 0; i < root.children.size(); i++) {
					preNode.children.add(root.children.get(i));
				}
				for (int i = 0; i < preNode.children.size(); i++) {
					preNode.children.get(i).fatherNode = root;
				}
				int indexPre = root.fatherNode.children.indexOf(preNode);
				preNode.keyList.add(root.fatherNode.keyList.get(indexPre));
				for (int i = 0; i < root.keyList.size(); i++) {
					preNode.keyList.add(root.keyList.get(i));
				}
				root.children = preNode.children;
				root.keyList = preNode.keyList;

				root.fatherNode.children.remove(preNode);
				preNode.fatherNode = null;
				preNode.keyList = null;
				preNode.children = null;
				root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
				// 更新链表
				if ((root.fatherNode.fatherNode != null
						&& (root.fatherNode.children.size() >= order / 2 && root.fatherNode.children.size() >= 2))
						|| root.fatherNode.fatherNode == null && root.fatherNode.children.size() >= 2) {
					return;
				}
				// 回溯更新父节点
				updateDelete(root.fatherNode);
				return;
			}

			// ⑥到这一步说明前阶段空了
			// 同后节点合并。
			if (nextNode != null && (nextNode.children.size() <= order / 2 || nextNode.children.size() <= 2)) {
				for (int i = 0; i < nextNode.children.size(); i++) {
					Node child = nextNode.children.get(i);
					root.children.add(child);
					child.fatherNode = root;
				}
				int index = root.fatherNode.children.indexOf(root);
				root.keyList.add(root.fatherNode.keyList.get(index));
				for (int i = 0; i < nextNode.keyList.size(); i++) {
					root.keyList.add(nextNode.keyList.get(i));
				}

				root.fatherNode.children.remove(nextNode);
				nextNode.fatherNode = null;
				nextNode.keyList = null;
				nextNode.children = null;
				root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
				// 更新链表
				if ((root.fatherNode.fatherNode != null
						&& (root.fatherNode.children.size() >= order / 2 && root.fatherNode.children.size() >= 2))
						|| root.fatherNode.fatherNode == null && root.fatherNode.children.size() >= 2) {
					return;
				}
				updateDelete(root.fatherNode);
				return;
			}
		}
	}

	/**
	 * 求B+树的高度
	 * 
	 * @param root
	 *            根节点
	 * @return
	 */
	private int height(Node root) {
		if (root == null)
			return 0;
		if (root.isLeaf())
			return 1;
		int height = 1;
		do {
			root = root.children.get(0);
			height++;
		} while (!root.isLeaf());
		return height;
	}

	/**
	 * 打印B+树
	 * 
	 * @param root
	 * @param head
	 */
	private void printTree(Node root, Node head) {
		int H = height(root);
		int h = H;
		// System.out.println("树高："+H);
		if (H == 0) {
			System.out.println("树空,无打印");
			return;
		} else {
			// System.out.println("446-H=="+H);
			System.out.println("打印树：");
			Queue<Node> queue = new LinkedList<>();
			queue.add(root);
			// 记录每层孩子个数
			int len = 1;
			while (h > 0) {
				int length = 0;
				for (int i = 0; i < len; i++) {
					Node curroot = queue.poll();
					if (curroot.isLeaf()) {
						for (int j = 0; j < curroot.keyAndValues.size(); j++) {
							System.out.print(curroot.keyAndValues.get(j).key + ",");
						}
					} else {
						for (int j = 0; j < curroot.keyList.size(); j++) {
							System.out.print(curroot.keyList.get(j) + ",");
						}
						for (int j = 0; j < curroot.children.size(); j++) {
							queue.add(curroot.children.get(j));
							length++;
						}
					}
					System.out.print("|");
				}
				System.out.println();
				len = length;
				h--;
			}
		}
		// 输出叶子节点value
		Node h1 = head;
		while (h1 != null) {
			for (int i = 0; i < h1.keyAndValues.size(); i++)
				System.out.print(h1.keyAndValues.get(i).value + "-");
			h1 = h1.nextNode;
			System.out.print("|");
		}
		System.out.print("\n");
	}

	public static void main(String args[]) {
		KeyAndValue keyAndValue1 = new KeyAndValue(1, "1");
		KeyAndValue keyAndValue2 = new KeyAndValue(2, "1");
		KeyAndValue keyAndValue3 = new KeyAndValue(3, "2");
		KeyAndValue keyAndValue4 = new KeyAndValue(4, "3");
		KeyAndValue keyAndValue5 = new KeyAndValue(5, "3");
		KeyAndValue keyAndValue6 = new KeyAndValue(6, "1");
		KeyAndValue keyAndValue7 = new KeyAndValue(7, "1");
		KeyAndValue keyAndValue8 = new KeyAndValue(8, "5");
		KeyAndValue keyAndValue9 = new KeyAndValue(9, "1");
		KeyAndValue keyAndValue10 = new KeyAndValue(10, "3");
		KeyAndValue keyAndValue11 = new KeyAndValue(11, "2");
		KeyAndValue keyAndValue12 = new KeyAndValue(12, "2");
		KeyAndValue keyAndValue13 = new KeyAndValue(13, "2");
		KeyAndValue keyAndValue14 = new KeyAndValue(14, "1");
		KeyAndValue keyAndValue15 = new KeyAndValue(15, "1");
		KeyAndValue keyAndValue16 = new KeyAndValue(16, "1");
		KeyAndValue keyAndValue17 = new KeyAndValue(17, "1");
		KeyAndValue keyAndValue18 = new KeyAndValue(18, "1");
		KeyAndValue keyAndValue19 = new KeyAndValue(19, "4");
		KeyAndValue keyAndValue20 = new KeyAndValue(20, "5");
		KeyAndValue keyAndValue21 = new KeyAndValue(21, "5");
		KeyAndValue keyAndValue22 = new KeyAndValue(22, "5");
		KeyAndValue keyAndValue23 = new KeyAndValue(23, "5");
		KeyAndValue keyAndValue24 = new KeyAndValue(24, "5");
		BPlusTreeOld t = new BPlusTreeOld(3);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue1);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue3);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue22);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue6);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue17);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue15);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue24);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue19);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue2);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue5);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue20);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue18);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue7);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue4);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue21);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue11);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue12);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue9);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue10);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue13);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue14);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue8);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue16);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue23);
		t.printTree(t.root, t.head);
		t.insert(t.root, keyAndValue23);
		t.printTree(t.root, t.head);

		System.out.println("键4对应的值为：" + t.search(4, t.root));
		System.out.println("键23对应的值为：" + t.search(23, t.root));
		System.out.println("键19对应的值为：" + t.search(19, t.root));
		System.out.println("键11对应的值为：" + t.search(11, t.root));
		System.out.println("键14对应的值为：" + t.search(14, t.root));
		System.out.println("键13对应的值为：" + t.search(13, t.root));
		t.delete(t.root, 23);
		t.printTree(t.root, t.head);
//		t.delete(t.root, 3);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 14);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 13);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 12);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 8);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 18);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 22);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 1);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 2);
//		t.printTree(t.root, t.head);
//		t.delete(t.root, 4);
//		t.printTree(t.root, t.head);

		// System.out.println("search13: "+t.search(33,t.root));

	}

}
